#include <iostream>
using namespace std;
// （13分）41、有两个一维数组 A[n]、res[n]，计算 A[i]与Aj乘积的最大值，并将其保存到res中。
// 若 A[]={1，4，-9，6}，则res[]=(6，24，81，36}。请设计时间空间上尽可能高效的算法MulMax，求res中各元素的值，函数原型为:
// void MulMax(int A，int res[]，int n)。
// ⑴ 给出算法的基本设计思想。
// ⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
// ⑶ 说明你所设计算法的时间复杂度。
// ————————————————

//                             版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

// 原文链接：https://blog.csdn.net/qq_52180526/article/details/144675595

// 7分的解法： 双层循环纯暴力求
void MulMax(int *A, int res[], int n)
{

    for (int i = 0; i < n; i++)
    {
        int max = A[i]; // 初始化 为自己本身

        for (int j = 0; j < n; j++)
        {
            if (A[i] * A[j] > max)
            {
                max = A[i] * A[j];
            }
        }
        res[i] = max;
    }
}

// 优化 记录正数最大 负数最小
void MulMax2(int *A, int res[], int n)
{

    int max = A[0];
    int min = A[0];

    for (int i = 0; i < n; i++)
    {
        if (A[i] > 0 && A[i] > max)
        {
            max = A[i]; // 记录最大值
        }

        if (A[i] < 0 && A[i] < min)
        {
            min = A[i]; // 记录最小值
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (A[i] == 0)
            res[i] = 0;
        if (A[i] > 0)
            res[i] = A[i] * max;

        if (A[i] < 0)
            res[i] = A[i] * min;
    }
}

int main()
{
    int arr[4] = {1, 4, -9, -10};
    int res[4];
    MulMax2(arr, res, 4);
    for (int i = 0; i < 4; i++)
    {
        printf("%d ", res[i]);
    }
    return 0;
}